#include <iostream>
#include <vector>
#include <deque>
#include <unordered_map>
#include <unordered_set>
#include <set>
#include <format>

using namespace std;

class Item
{
    public:
    Item()
    {
        cout << "constructor called" << endl;
    }

    Item(int num)
    {
        this->num = num;
        cout << format("{} constructor called!", this->num) << endl;
    }

    Item(const Item &item)
    {
        this->num = item.num;
        cout << format("item {0} copy constructor called!", item.num) << endl;
    }

    ~Item()
    {
        cout << "destructor called" << endl;
    }
    bool operator<(const Item &a) const
    {
        return this->num < a.num;
    }
    int num;
};


int main()
{
    //顺序容器 使用结构是内置数组 按照插入的先后顺序排序 array vector deque list forward_list
    //实时插入排序 选择set map 非实时插入排序 选vector
    Item item(1);
    Item item1(2);
    cout << "construct finished" << endl;
    vector<Item> vector(2); //C++容器是值语义 加入容器会调用拷贝构造函数，如果对象比较复杂那么加入容器的过程成本很高
    vector.push_back(item);
    vector.push_back(item1);
    cout << vector.capacity() << endl;
    cout << vector.size() << endl;
    cout << vector.max_size() << endl;


    //有序容器 使用结构为树结构通常是红黑树 元素插入容器时按照某种规则自动重新调整次序  有序容器中集合使用set 映射使用map
    //由于有序容器插入时会自动排序所以当数据量大的时候 插入排序的成本需要考虑进去
    deque<Item> deq;
    deq.push_back(item);
    //不建议通过在容器中存放指针来间接保存元素 由于是间接持有 所以就不能利用容器自动销毁元素的特性了 如果要用建议使用shared_ptr 但是unique_ptr是转移语义 控制指针所有权比较难

    //set中放置自定义元素 第一种方法需要重载比较操作符
    set<Item> s;
    s.emplace(item); 
    s.emplace(item1);
    for (auto &i : s)
    {
        cout << "s: " << i.num << endl;
    }
    //第二种方法 提供比较函数
    auto comp = [](const Item &a, const Item &b)
    {
        return a.num < b.num;
    };
    set<Item, decltype(comp)> gs(comp);
    gs.emplace(item);
    gs.emplace(item1);
    for (auto &i : gs)
    {
        cout << "s: " << i.num << endl;
    }

    //无序容器 unordered_set unordered_multiset unordered_map unordered_multimap
    //使用结构为哈希表
    unordered_map<int, string> dict;
    dict[0] = "1";
    dict.emplace(1, "2");
    dict[2] = "3";
    for (auto &i : dict)
    {
        cout << "dict: " << i.second << endl;
    }
    //没有排序需求 应该用无序容器 但是注意散列表理论上的时间复杂度是O(1) 比红黑树的O(longN)快 不过如果对元素里大量数据计算散列值这个常数可能会很大 也许会超过O(logN)
    //还有如果散列值不均匀有散列值冲突 那么性能还会进一步降低最差成了O(n)

    unordered_set<Item, string> items;
    dict[0] = "1";
    dict.emplace(1, "2");
    dict[2] = "3";
    for (auto &i : dict)
    {
        cout << "dict: " << i.second << endl;
    }
}